画布 1
内存管理
  主存管理概述
    存储器：能接收和保存数据、并根据命令提供这些数据的装置，分为主存和辅存。
      主存
        内存
      辅村
        磁盘
    主存共享方式
      大小不同
        ① 分区存储管理
        ② 段式存储管理
      大小相等的区域
        页式存储管理
      段页式存储管理
    逻辑组织
      一维地址结构
        一个程序是一个连续、线性的地址结构；
        确定线性地址空间中的指令地址或操作数地址只需要一个信息。
        可以把程序的地址结构近似成一维数组,是一段连续的线形分布的空间,只需要一个信息就可以确定地址.
      二维地址结构
        一个程序由若干个分段组成，每个分段是一个连续的地址区
        确定线性地址空间中的指令地址或操作数地址需要两个信息，一是该信息所在的分段，另一个是该信息在段内的偏移量。
  主存管理的功能
    几个概念
      物理地址是计算机主存单元的真实地址，又称为绝对地址和实地址
      物理地址的集合所对应的空间组成了主存空间。
      用户的程序地址 (指令地址或操作数地址)均为逻辑地址。
      程序地址空间:用户程序所有的逻辑地址集合对应的空间。
    主存管理功能
      实现逻辑地址到物理主存地址的映射
        逻辑地址变换成主存中的物理地址的过程,称为地址映射.
        地址映射的时机
          编译的时候确定地址映射的关系
          在程序装入的时候确定地址映射关系,静态地址映射:程序代码的逻辑地址和存储空间的映射在程序装入内存的时候就已经确定了,由重定位装入程序确定
          在程序运行时确定地址映射关系:在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射，这种地址变换方式称为动态地址映射。(重定位寄存器)
      主存分配
        主存资源信息块：等待队列；空闲区队列；主存分配程序
      存储保护
        主存按照区的模式分配给各用户程序使用,每个用户程序必须在给定的存储区域内活动即可.
        上下界保护
          有上界寄存器和下界寄存器,程序访问内存只能使用在上界寄存器和下界寄存器之间的区域(物理地址)
        基址、限长寄存器保护
          有限长寄存器,和基址寄存器,基址寄存器表示程序在内存中存储空间从何开始,限长寄存器限制程序访问的逻辑地址,逻辑地址<限长寄存器的值
      主存扩充
        可行性
          局部性特征
            时间局部性:一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内
            空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小区域内
            分支局部性：一条跳转指令的两次执行，很可能跳到相同的内存位置
        实现方法
          程序的全部代码和数据存放在辅存中；
          将程序当前执行所涉及的那部分程序代码放入主存中；
          程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行。
        虚拟存储器
          由OS和硬件相配合完成主存和辅存之间信息的动态调度,这样子好像OS提供了一个存储容量比实际主存大得多的存储器,这个存储器称之为虚拟存储器
            逻辑地址与物理地址分开
            存储空间与虚地址空间分开
            提供地址变换机构
          用户通过逻辑地址访问虚拟存储器,接着OS和硬件动态调度,将虚拟存储器的逻辑地址转化为物理地址来访问实际的主存
  分区存储管理
    静态分区
      把内存预先划分成多个分区，分区大小可以相同或不同
      分区个数固定，分区大小固定
      一个分区装入一个作业
      主存分区是如何的已经在运行前就已经确定了
    动态分区
      在运行程序的过程中:建立分区,依照用户请求的大小分配分区
    分区分配所需要的数据结构
      M_RIB
        主存资源信息块
          等待队列头指针
          空闲区队列头指针
          主存分批程序入口地址
      分区描述器(PD)
        flag为0为空闲区
        flag为1是已占用区
        size是分区大小
        next:如果是空闲区,那就是下一个空闲区的首地址,如果是已分配区,这一项为0
    分区回收的思路
      检查释放分区的在主存中的连接情况
      如果上下邻接空闲区,则合并,成为一个新的空闲区
      若回收分区不与任何空闲去相邻接,建立一个新的空闲区,加入到空闲队列.
    选择空闲区的放置策略
      首次适应算法:是将输入的程序放置到主存里足够装入它的 地址最低的 空闲区中。(地址最低最好)
        放入一个能放入这个程序的空闲块,空闲块地址越低越好.
        空闲区队列:空闲区地址由低到高排序
      最佳适应算法:最佳适应算法是将输入的程序放置到主存中与它所需大小最接近的空闲区中.
        放入一个能放入这个程序的空闲块,空闲块大小越小越好.
        空闲区队列:由小到大排序
      最坏适应算法是将输入的程序放置到主存中与它所需大小差距最大的空闲区中,
        放入一个能放入这个程序的空闲块,空闲块大小越低越好.
        空闲区队列:由大到小排序
    碎片问题
      在已分配的区域里面存在着一些没有被充分利用的空闲区.
      解决技术
        拼接技术
          移动存储器中某些已分配区中的信息,使得本来分散的空闲区连接成比较大的空闲区
        对换技术
          选择内存中的某个进程暂时移出到磁盘，腾出空间给其他进程，同时把磁盘中的某个进程换进主存使其投入运行
        伙伴系统
          把一个大的存储块分为大小相等的两个小存储区（互为伙伴，大小均为2的K次幂）
          分配过程
            由小到大在空闲块数组中寻找到最小的可用空闲块.
            如果空闲块过大,就用可用空闲块二等分,直到得到合适的可用空闲块
            空闲块的大小只可能是2的n次方.若程序大小是s,且满足2^{k-1}<s≤2^k,那么就把大小为2^k次的分区分配
          释放过程
            把释放的块加入空闲块数组
            合并满足合并条件的空闲块
              大小相同
              地址相邻
              且低地址空闲块是2^{i+1}的位数
  页式存储管理
    基本概念
      程序的地址空间(虚拟地址空间)被等分成大小相等的片,称为页面,又称为虚页
      主存(物理地址空间,实地址空间)又被分成大小相等的片,称为主存块,又称为实页
      为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表。(程序逻辑地址中虚页号与物理主存中实页号之间的变换映射)
        程序逻辑地址有虚页号,内存的物理地址里面为实页号,程序就通过虚页号替换成实页号来找到程序或数据实际的位置.
        总的来说,是记录页和块之间对应关系的地址变换的结构
    页式地址变换
      虚地址(程序逻辑地址)结构
        其中高位为页号P
        低位为页内偏移
      地址变换过程
        CPU给出操作数
        分页机构自动把逻辑地址分成两部分高地址页号为P,低地址页内偏移为W
        根据页表始址寄存器指示的首地址PTBR,加上页号P,就是该页号对应的页表项的地址(PTBR+P就是这个页对应的页表项地址),获得物理块块号
        将块号B和页内偏移量并在一起,就形成了主存地址(物理地址)
      快表TLB
        先在快表中查找有没有相关页表项记录,快表是一个独立的硬件,独立于内存之外
        如果快表中没有,只能查找存储在内存中的页表,然后把查出来的页表项记录在快表里面
      多级页表
        间接引用
        页表项中可能存储的不是物理块号,而是下一级页表的首地址
    请调页面的机制
      简单页式系统
        装入一个程序的全部页面才能投入运行。
      请求页式系统
        装入一个程序的部分页面即可投入运行。
      扩充页表
        加一个中断位,表示此页是不是在主存里面,如果是0表示在主存,如果为1表示不在主存
      缺页中断
        缺页中断就是要访问的虚页(逻辑地址对应的虚页)不在主存，需要操作系统将其调入主存后再进行访问。
        缺页中断的处理
          如果没有空闲块(物理内存对应的实页),则需要选一个虚页淘汰,这个虚页对应的主存块重新分配.(一个程序只会分配若干个空闲块(内存空间),如果不够就要淘汰对应一页中的一块)
一般来说就是选择一个页表的页表项中断位为1
对应的主存块分配给另外一页.
          然后从外存中调入所需的页
          调整页表
        抖动
          简单地说，导致系统效率急剧下降的主存和辅存之间的频繁的页面置换现象.
      淘汰策略
        选择淘汰掉哪一页的规则叫做置换策略,决定淘汰哪一页
        一般来说淘汰出现在分配的主存块数比程序逻辑地址页数少的情况下
        具体的淘汰策略
          FIFO算法
            总是选择在主存中居留时间最长的那一页
            实现的数据结构
              页号表
                用一个变量k来表示下一次替换哪一页,用一个数组p记录页号,要替换的页=p[k],然后p[k]=新的页号,k++
              存储分块表
                构建一个队列,队列的每个元素都是(页号,块号)
                每次选一个出队,出队元素对应的页号淘汰
                出队元素的页号替换成新分配页面的页号,块号不变,再进入队尾
          LRU(最久未使用)算法
            软件方法：采用页号栈
              页号对应的是一个栈
              假如说访问了某个页,这个页号进入栈底
              要淘汰某个元素了,栈顶元素出栈(栈顶元素对应的页号被淘汰),新的页号放入栈底
  段式及段页式存储管理
    段式地址空间
      由若干个逻辑分段组成，每个分段有自己的名字，对于一个分段而 言，它是一个连续的地址区。
      段:程序中一组逻辑意义完整的信息集合.
      段式地址变换
        取出程序地址(s，w)；其中s为段号,w为段内位移
        用s检索段表；找到该段的起始地址B
        如w＜0或w≥L则主存越界；
        (B＋w)即为所需主存地址
    段页式系统
      段页式地址变换
        首先还是一样程序地址(s,p,w)其中s为段号,p为该段内的页号,w为页内偏移
        首先根据s的数码找到这个段的页表始址PTEP
        根据物理地址和页内偏移找到最后的主存地址